package com.lizk.union_find;

/**
 * 优化，基于rank，当前节点到根节点的层数，应该优于基于size的优化
 * 并查集，解决连接问题
 * 网络中的两个节点是否相连？
 * 以数组存储数据，以链的形式表示是否相连
 * 1.用数组来存储每个节点
 * 2.每个节点都有一个parent，parent表示当前节点的父节点
 * 3.相同顶节点的节点为相连的节点
 * 4.已经是顶节点的节点的父节点是自己的索引
 * 5.当两个合并两个节点的时候，就是让一个节点的顶节点作为另一个节点顶节点的子节点
 * @author lizhikui
 * @date 2020/2/14 16:19
 */
public class UnionFindLinkOptimizeByRank {
    public static class Node{
        int id;
        int rank;
        int parent;
    }

    Node[] nodes ;

    public UnionFindLinkOptimizeByRank(int length){
        nodes = new Node[length];
        for (int i = 0; i < length; i++) {
            Node node = new Node();
            node.id = i ;
            node.parent = i;
            node.rank = 1;
            nodes[i] = node;
        }
    }

    private int find (int id){

        /*
            这里使用了“压缩路径”的方法优化了find的操作
            1.检查当前节点是否为根节点
            2.如果不是跟节点，那么让当前节点的父节点指向当前父节点的父节点，这样跳过一个层次
            3.重复以上两个步骤，知道找到根节点
        */
        /*
            Node n = nodes[id];
            while(n.parent != n.id){
            n.parent = nodes[n.parent].parent;
            n = nodes[n.parent];
        }*/


        /*
            这里也是“路径压缩”优化
            这里更进一步，把所有的树都压缩成只有两层的结构
         */
        if (nodes[id].parent != id){
            nodes[id].parent = find(nodes[id].parent);
        }
        return nodes[id].parent;
    }

    public void union (int one,int two){
        if (isConn(one,two)){
            return;
        }
        int oneRootIndex = find(one);
        int twoRootIndex = find(two);
        Node oneRoot = nodes[oneRootIndex];
        Node twoRoot = nodes[twoRootIndex];

        if (oneRoot.rank > twoRoot.rank){
            twoRoot.parent = oneRoot.parent;
        }else if((oneRoot.rank < twoRoot.rank)){
            oneRoot.parent = twoRoot.parent;
        }else {
            oneRoot.parent = twoRoot.parent;
            twoRoot.rank = twoRoot.rank + 1;
        }

    }

    public boolean isConn(int one,int two){
        return find(one) == find(two);
    }

}
